Also zurück zu dem Thema, wo wir gestern aufgehört haben. Wir haben uns gestern

beschäftigt mit verketteten Listen und können die verketteten Listen als ein

Spezialfall von Bäumen ansehen. Also ein Baum kann jetzt angesehen werden als eine

Verallgemeinerung von Listen. Warum? In der Liste hat jedes Element exakt einen

Nachfolger. Bei einem Baum hat jedes Element mehrere Nachfolger. Wir nennen

diese Nachfolger, ich gehe jetzt einfach die Folien ziemlich ablesend durch, weil

die sind im Prinzip Begriffe, die man dann immer wieder gebraucht. Also ein

Nachfolger ist ein Child oder ein Kindknoten und analog zu Listen hat

eben jedes Element genau einen Vorgänger. Also der wird in der Regel als

Parentknoten oder Parent Note oder Elternknoten benannt.

Es gibt einen ausgezeichneten Knoten, der keinen Elternknoten hat. Das ist die

Wurzel des Baumes und alle Knoten, die keine Kinderknoten haben, das sind die

Blätter des Baumes oder Terminalknoten und Knoten mit Kinderknoten heißen auch

innere Knoten.

Und wir können jetzt jeden Knoten von diesem Baum auch also eine Ebene zuordnen

und diese Ebene, das ist die Länge des Pfades, wenn wir von der Wurzel ausgehen

bis wir zu diesem Knoten kommen. Die Höhe eines Baumes, das ist die maximale

Ebene, also die Höhe ist bestimmt durch den Knoten, der die maximale Länge eines

Pfades hat. Der Verzweigungsgrad eines Knotens ist die Anzahl der Kinderknoten

und ein sehr wichtiger Spezialfall ist die Situation, wo ein Baum, wo ein Knoten

maximal zwei Nachfolger hat, das sind die sogenannten Binärbäume. Wir können

diese Bäume visualisieren. Ich habe hier mal ein Beispiel. Was machen wir? Wir

verbinden die Eltern und die Kinderknoten. Hier ein Beispiel und aufpassen, ich habe

das absichtlich schlecht gemalt oder so gemalt, dass man sich durchs Auge

deuschen lassen kann und wie ich gestern schon gesagt habe, in der Informatik

wachsen die Bäume von oben nach unten. Also wir haben hier die Wurzel, das

ausgezeichnete Element. Die Wurzel hat keinen Vorgänger. Von der Wurzel aus, die

Wurzel ist der Elternknoten für die Knoten 2, 4 und 3. Für 5 und 6 ist 3 der

Elternknoten. Die Wurzel liegt auf der Ebene 0. Ich muss 0 Pfade gehen, um von der

Wurzel zur Wurzel zu kommen, ist klar. Und hier ein bisschen anders gezeichnet, das

Auge suggeriert, dass es da weiter unten ist, aber die Ebene 1, das sind die Knoten

genau 2, 3 und 4. Und 5 und 6 haben die Ebene 2, weil ich von der Wurzel aus 2,

einen Pfadelänge 2 zurücklegen muss, um hinzukommen. Und es ist natürlich kein

Binärbaum, ganz klar, denn einer der Knoten hat 3 Nachfolger, 3 Kinder. Soweit

klar? Gut. Bäume sind ganz extrem wichtig. Die werden immer wieder als

Landstruktur verwendet. Ein Beispiel, das wir dann auch sehen werden, das sind

Ableitungsbäume bezüglich einer Grammatik. Und zwar nicht nur bezüglich

einer Grammatik im linguistischen Sinn, sondern auch einer Grammatik für

Programmiersprachen. Also wenn unser Programm an einen Compiler übergeben

wird, dann ist ein Teil davon, das werden wir im nächsten Kapitel noch mal

anschauen, die Syntax-Analyse. Also die Frage, wie ist dieses Programm aufgebaut?

Diese Struktur-Analyse, die muss eindeutig sein. In einer natürlichen

Sprache ist dieses Syntax oft nicht eindeutig.

Es gibt ein paar so schöne Beispielsätze. Einer der bekanntesten in der

Linguistik ist der Satz, time flies like an arrow.

Jetzt können Sie sich mal überlegen, bis zum nächsten Dienstag, ist dieser Satz,

ist diese Sequenz von Wörtern eindeutig oder gibt es da unterschiedliche

Interpretationen? Und diese unterschiedlichen Interpretationen, die

kann ich dadurch visualisieren, dass ich diesen Syntax-Baum mehr aufbaue, wo ich

dann Satzteile wie Nominalfraße, Verbalfraße als Knoten andeute.